{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary String With Substrings Representing 1 To N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: queryString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子串能表示从 1 到 N 数字的二进制串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制字符串&nbsp;<code>s</code>&nbsp;和一个正整数&nbsp;<code>n</code>，如果对于&nbsp;<code>[1, n]</code>&nbsp;范围内的每个整数，<em>其二进制表示都是&nbsp;<code>s</code> 的 <strong>子字符串</strong> ，就返回 <code>true</code>，否则返回 <code>false</code>&nbsp;</em>。</p>\n",
    "\n",
    "<p><strong>子字符串</strong>&nbsp;是字符串中连续的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0110\", n = 3\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0110\", n = 4\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;不是&nbsp;<code>'0'</code>&nbsp;就是&nbsp;<code>'1'</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-string-with-substrings-representing-1-to-n](https://leetcode.cn/problems/binary-string-with-substrings-representing-1-to-n/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-string-with-substrings-representing-1-to-n](https://leetcode.cn/problems/binary-string-with-substrings-representing-1-to-n/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"0110\"\\n3', '\"0110\"\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        \n",
    "        s = s[::-1]\n",
    "        num_str = ['0']\n",
    "        \n",
    "        for num in range(1, n+1):\n",
    "\n",
    "            # 进位\n",
    "            i = 0\n",
    "            while int(num_str[i]) ^ 1 == 0:\n",
    "                num_str[i] = '0'\n",
    "                i = i+1\n",
    "                if len(num_str) == i:\n",
    "                    num_str += '1'\n",
    "                    break\n",
    "            \n",
    "            if len(num_str) != i:\n",
    "                num_str[i] = '1'\n",
    "\n",
    "            if ''.join(num_str) not in s:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n>302:\n",
    "            return False\n",
    "        for i in range(1,n+1):\n",
    "            if str(bin(i))[2:] not in s:#i转为二进制不在\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # ans=0\n",
    "        # m=len(s)\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[m-i-1]=='1':\n",
    "        #         ans+=2**(i)\n",
    "        # print(ans)\n",
    "        # if ans==0:\n",
    "        #     return False\n",
    "        # if n==1:\n",
    "        #     return True\n",
    "        # for i in range(n,1,-1):\n",
    "        #     if ans%i!=0 and ans%i!=1:\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "\n",
    "        # if n == 1:\n",
    "        #     return '1' in s\n",
    "\n",
    "        # m = len(s)\n",
    "        # k = n.bit_length() - 1\n",
    "        # if m < max(n - (1 << k) + k + 1, (1 << (k - 1)) + k - 1):\n",
    "        #     return False\n",
    "\n",
    "        # # 对于长为 k 的在 [lower, upper] 内的二进制数，判断这些数 s 是否都有\n",
    "        # def check(k: int, lower: int, upper: int) -> bool:\n",
    "        #     if lower > upper: return True\n",
    "        #     seen = set()\n",
    "        #     mask = (1 << (k - 1)) - 1\n",
    "        #     x = int(s[:k - 1], 2)\n",
    "        #     for c in s[k - 1:]:\n",
    "        #         # & mask 可以去掉最高比特位，从而实现滑窗的「出」\n",
    "        #         # << 1 | int(c) 即为滑窗的「入」\n",
    "        #         x = ((x & mask) << 1) | int(c)\n",
    "        #         if lower <= x <= upper:\n",
    "        #             seen.add(x)\n",
    "        #     return len(seen) == upper - lower + 1\n",
    "        # return check(k, n // 2 + 1, (1 << k) - 1) and check(k + 1, 1 << k, n)\n",
    "        return len(s)>=len(bin(n))-2 and all(bin(i)[2:] in s for i in range(1,n+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(1, n+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        \n",
    "        for num in range(1, n+1):\n",
    "            num_list = []\n",
    "\n",
    "            while num != 0:\n",
    "                num_list.append(str(num%2))\n",
    "                num = int(num/2)\n",
    "            \n",
    "            num_list = num_list[::-1]\n",
    "\n",
    "            if ''.join(num_list) not in s:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n>302:# 1000lg2=301.03 s最多表示302位的数字\n",
    "            return False\n",
    "        for i in range(n,n//2,-1):#x的二进制是子串,那么x/2也是,所以只需要判断后面一半\n",
    "            if str(bin(i))[2:] not in s:#i转为二进制不在s中,二进制字符串以0b开头需要截取\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # ans=0\n",
    "        # m=len(s)\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[m-i-1]=='1':\n",
    "        #         ans+=2**(i)\n",
    "        # print(ans)\n",
    "        # if ans==0:\n",
    "        #     return False\n",
    "        # if n==1:\n",
    "        #     return True\n",
    "        # for i in range(n,1,-1):\n",
    "        #     if ans%i!=0 and ans%i!=1:\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "\n",
    "        # if n == 1:\n",
    "        #     return '1' in s\n",
    "\n",
    "        # m = len(s)\n",
    "        # k = n.bit_length() - 1\n",
    "        # if m < max(n - (1 << k) + k + 1, (1 << (k - 1)) + k - 1):\n",
    "        #     return False\n",
    "\n",
    "        # # 对于长为 k 的在 [lower, upper] 内的二进制数，判断这些数 s 是否都有\n",
    "        # def check(k: int, lower: int, upper: int) -> bool:\n",
    "        #     if lower > upper: return True\n",
    "        #     seen = set()\n",
    "        #     mask = (1 << (k - 1)) - 1\n",
    "        #     x = int(s[:k - 1], 2)\n",
    "        #     for c in s[k - 1:]:\n",
    "        #         # & mask 可以去掉最高比特位，从而实现滑窗的「出」\n",
    "        #         # << 1 | int(c) 即为滑窗的「入」\n",
    "        #         x = ((x & mask) << 1) | int(c)\n",
    "        #         if lower <= x <= upper:\n",
    "        #             seen.add(x)\n",
    "        #     return len(seen) == upper - lower + 1\n",
    "        # return check(k, n // 2 + 1, (1 << k) - 1) and check(k + 1, 1 << k, n)\n",
    "        return len(s)*(len(s)+1)//2>=n and all([bin(i)[2:] in s for i in range(1,n+1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # 4 = \"100\"\n",
    "        # 如果 4 符合 那么 2 也符合\n",
    "        # 所以应该只要判断 n ~ n / 2 之间的数\n",
    "\n",
    "\n",
    "        for i in range(n, n >> 1, -1):\n",
    "            x = bin(i)[2:]\n",
    "            if x not in s:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(max(1, n //2 ), n+1):\n",
    "            if not bin(i)[2:] in s:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1,n+1):\n",
    "            if bin(i)[2:] not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # # 1. 暴力枚举\n",
    "        # return all(bin(i)[2:] in s for i in range(1, n +1))\n",
    "\n",
    "\n",
    "        # 2. 处理s的子串\n",
    "        # seen = set()\n",
    "        # s = list(map(int, s)) # 把s[i]全部换成int\n",
    "        # for i, x in enumerate(s):\n",
    "        #     if x == 0: continue #二进制数从1开始\n",
    "        #     j = i + 1 #下一个字符的下标\n",
    "\n",
    "        #     while x <= n:\n",
    "        #         seen.add(x)\n",
    "        #         if j == len(s): break\n",
    "        #         x = (x << 1) | s[j] # 子串s[i:j + 1]的二进制数\n",
    "        #         j += 1\n",
    "        # return len(seen) == n\n",
    "        \n",
    "        # 3.滑动窗口代替循环\n",
    "        if n == 1:\n",
    "            return '1' in s\n",
    "        m = len(s)\n",
    "        k = n.bit_length() - 1\n",
    "        if m < max(n - (1 << k) + k + 1, (1 << (k - 1)) + k - 1):\n",
    "            return False\n",
    "        \n",
    "        # 对于长为k的在[lower, upper]内的二进制数，判断这些数是否都有\n",
    "        def check(k:int, lower:int, upper:int) -> bool:\n",
    "            if lower > upper: return True\n",
    "            seen = set()\n",
    "            mask = (1 << (k - 1)) - 1\n",
    "            x = int(s[:k - 1], 2)\n",
    "            for c in s[k - 1:]:\n",
    "                x = ((x &mask) << 1) | int(c)\n",
    "                if lower <= x <= upper:\n",
    "                    seen.add(x)\n",
    "            return len(seen) == upper - lower + 1\n",
    "        return check(k, n // 2 + 1, (1 << k) - 1) and check(k +1, 1 << k, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # ans=0\n",
    "        # m=len(s)\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[m-i-1]=='1':\n",
    "        #         ans+=2**(i)\n",
    "        # print(ans)\n",
    "        # if ans==0:\n",
    "        #     return False\n",
    "        # if n==1:\n",
    "        #     return True\n",
    "        # for i in range(n,1,-1):\n",
    "        #     if ans%i!=0 and ans%i!=1:\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "\n",
    "        # if n == 1:\n",
    "        #     return '1' in s\n",
    "\n",
    "        # m = len(s)\n",
    "        # k = n.bit_length() - 1\n",
    "        # if m < max(n - (1 << k) + k + 1, (1 << (k - 1)) + k - 1):\n",
    "        #     return False\n",
    "\n",
    "        # # 对于长为 k 的在 [lower, upper] 内的二进制数，判断这些数 s 是否都有\n",
    "        # def check(k: int, lower: int, upper: int) -> bool:\n",
    "        #     if lower > upper: return True\n",
    "        #     seen = set()\n",
    "        #     mask = (1 << (k - 1)) - 1\n",
    "        #     x = int(s[:k - 1], 2)\n",
    "        #     for c in s[k - 1:]:\n",
    "        #         # & mask 可以去掉最高比特位，从而实现滑窗的「出」\n",
    "        #         # << 1 | int(c) 即为滑窗的「入」\n",
    "        #         x = ((x & mask) << 1) | int(c)\n",
    "        #         if lower <= x <= upper:\n",
    "        #             seen.add(x)\n",
    "        #     return len(seen) == upper - lower + 1\n",
    "        # return check(k, n // 2 + 1, (1 << k) - 1) and check(k + 1, 1 << k, n)\n",
    "        return len(s)>=len(bin(n))-2 and all(bin(i)[2:] in s for i in range(1,n+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1,n+1):\n",
    "            if bin(i)[2:] not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # ans=0\n",
    "        # m=len(s)\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[m-i-1]=='1':\n",
    "        #         ans+=2**(i)\n",
    "        # print(ans)\n",
    "        # if ans==0:\n",
    "        #     return False\n",
    "        # if n==1:\n",
    "        #     return True\n",
    "        # for i in range(n,1,-1):\n",
    "        #     if ans%i!=0 and ans%i!=1:\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "\n",
    "        # if n == 1:\n",
    "        #     return '1' in s\n",
    "\n",
    "        # m = len(s)\n",
    "        # k = n.bit_length() - 1\n",
    "        # if m < max(n - (1 << k) + k + 1, (1 << (k - 1)) + k - 1):\n",
    "        #     return False\n",
    "\n",
    "        # # 对于长为 k 的在 [lower, upper] 内的二进制数，判断这些数 s 是否都有\n",
    "        # def check(k: int, lower: int, upper: int) -> bool:\n",
    "        #     if lower > upper: return True\n",
    "        #     seen = set()\n",
    "        #     mask = (1 << (k - 1)) - 1\n",
    "        #     x = int(s[:k - 1], 2)\n",
    "        #     for c in s[k - 1:]:\n",
    "        #         # & mask 可以去掉最高比特位，从而实现滑窗的「出」\n",
    "        #         # << 1 | int(c) 即为滑窗的「入」\n",
    "        #         x = ((x & mask) << 1) | int(c)\n",
    "        #         if lower <= x <= upper:\n",
    "        #             seen.add(x)\n",
    "        #     return len(seen) == upper - lower + 1\n",
    "        # return check(k, n // 2 + 1, (1 << k) - 1) and check(k + 1, 1 << k, n)\n",
    "        return all(bin(i)[2:] in s for i in range(1,n+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(1, n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n>302:#log_2 1000\n",
    "            return False\n",
    "        for i in range(n,n//2,-1):#x的二进制是子串,那么x/2也是,所以只需要判断后面一半\n",
    "            if str(bin(i))[2:] not in s:#i转为二进制不在s中,二进制字符串以0b开头需要截取\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(1,n+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1, n+1):\n",
    "            if s.find(bin(i)[2:]) == -1:\n",
    "                return False\n",
    "                break\n",
    "            else:\n",
    "                pass\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        candidates = set()\n",
    "        for length in range(1, 11):\n",
    "            for idx in range(len(s)-length+1):\n",
    "                candidates.add(int(s[idx: idx+length], 2))\n",
    "        for i in range(1, n+1):\n",
    "            if i not in candidates:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(n):\n",
    "            if str(bin(i+1))[2:] not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n>302:# 1000lg2=301.03  s最多表示302位的数\n",
    "            return False\n",
    "        for i in range(1,n+1):\n",
    "            if str(bin(i))[2:] not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(n,0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        def help(s, k, mi, ma):\n",
    "            st = set()\n",
    "            t = 0\n",
    "            for r in range(len(s)):\n",
    "                t = t * 2 + int(s[r])\n",
    "                if r >= k:\n",
    "                    t -= int(s[r-k]) << k\n",
    "                if r >= k-1 and t >= mi and t <= ma:\n",
    "                    st.add(t)\n",
    "            return len(st) == ma-mi+1\n",
    "        if n == 1:\n",
    "            return '1' in s\n",
    "        k = 15\n",
    "        while (1<<k) >= n:\n",
    "            k -= 1\n",
    "        if len(s) < (1<<(k-1))+k-1 or len(s) < n - (1<<k) + k + 1:\n",
    "            return False\n",
    "        return help(s, k, 1<<(k-1), (1<<k)-1) and help(s, k+1, 1<<k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        seen = set()\n",
    "        s = list(map(int, s))  # 把 s[i] 全部转成 int\n",
    "        for i, x in enumerate(s):\n",
    "            if x == 0: continue  # 二进制数从 1 开始\n",
    "            j = i + 1  # 下一个字符的下标\n",
    "            while x <= n:\n",
    "                seen.add(x)\n",
    "                if j == len(s): break\n",
    "                x = (x << 1) | s[j]  # 子串 s[i:j+1] 的二进制数\n",
    "                j += 1\n",
    "        return len(seen) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(1, n + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(max(1,n//2-1),n+1):\n",
    "            k = bin(i)\n",
    "            if k[2:] not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        def help(s, k, mi, ma):\n",
    "            st = set()\n",
    "            t = 0\n",
    "            for r in range(len(s)):\n",
    "                t = t * 2 + (int)(s[r])\n",
    "                if r >= k:\n",
    "                    t -= int(s[r - k]) << k\n",
    "                if r >= k - 1 and t >= mi and t <= ma:\n",
    "                    st.add(t)\n",
    "            return len(st) == ma - mi + 1\n",
    "        if n == 1:\n",
    "            return s.find('1') != -1\n",
    "        k = 30\n",
    "        while (1 << k) >= n:\n",
    "            k -= 1\n",
    "        if len(s) < (1 << (k - 1)) + k - 1 or len(s) < n - (1 << k) + k + 1:\n",
    "            return False\n",
    "        return help(s, k, 1 << (k - 1), (1 << k) - 1) and help(s, k + 1, 1 << k, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        def help(s, k, mi, ma):\n",
    "            st = set()\n",
    "            t = 0\n",
    "            for r in range(len(s)):\n",
    "                t = t * 2 + (int)(s[r])\n",
    "                if r >= k:\n",
    "                    t -= int(s[r - k]) << k\n",
    "                if r >= k - 1 and t >= mi and t <= ma:\n",
    "                    st.add(t)\n",
    "            return len(st) == ma - mi + 1\n",
    "        if n == 1:\n",
    "            return s.find('1') != -1\n",
    "        k = 30\n",
    "        while (1 << k) >= n:\n",
    "            k -= 1\n",
    "        if len(s) < (1 << (k - 1)) + k - 1 or len(s) < n - (1 << k) + k + 1:\n",
    "            return False\n",
    "        return help(s, k, 1 << (k - 1), (1 << k) - 1) and help(s, k + 1, 1 << k, n)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        sl = len(s)\n",
    "        st = set()\n",
    "        for i in range(sl):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            t = 1\n",
    "            j = i + 1\n",
    "            while t <= n:\n",
    "                st.add(t)\n",
    "                if j == sl:\n",
    "                    break\n",
    "                t = (t << 1) + int(s[j])\n",
    "                j += 1\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        hashMap = set()\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            value = 0\n",
    "            for j in range(i, len(s)):\n",
    "                value = (value << 1) + (ord(s[j]) - 48)\n",
    "                if value > n:\n",
    "                    break\n",
    "                hashMap.add(value)\n",
    "        \n",
    "        return len(hashMap) >= n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        sl = len(s)\n",
    "        st = set()\n",
    "        for i in range(sl):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            t = 1\n",
    "            j = i + 1\n",
    "            while t <= n:\n",
    "                st.add(t)\n",
    "                if j == sl:\n",
    "                    break\n",
    "                t = (t << 1) + int(s[j])\n",
    "                j += 1\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1, n+1):\n",
    "            if bin(i)[2:] not in s:\n",
    "                return False\n",
    "                break\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # 1. 暴力枚举\n",
    "        return all(bin(i)[2:] in s for i in range(1, n +1))\n",
    "\n",
    "\n",
    "        # 2. 处理s的子串\n",
    "        seen = set()\n",
    "        s = list(map(int, s)) # 把s[i]全部换成int\n",
    "        for i, x in enumerate(s):\n",
    "            if x == 0: continue #二进制数从1开始\n",
    "            j = i + 1 #下一个字符的下标\n",
    "\n",
    "            while x <= n:\n",
    "                seen.add(x)\n",
    "                if j == len(s): break\n",
    "                x = (x << 1) | s[j] # 子串s[i:j + 1]的二进制数\n",
    "                j += 1\n",
    "        return len(seen) == n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n>302:# 1000lg2=301.03 s最多表示302位的数字\n",
    "            return False\n",
    "        for i in range(n,n//2,-1):#x的二进制是子串,那么x/2也是,所以只需要判断后面一半\n",
    "            if str(bin(i))[2:] not in s:#i转为二进制不在s中,二进制字符串以0b开头需要截取\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n==1:\n",
    "            return bool(\"1\" in s)\n",
    "        for i in range(1,n+1):\n",
    "            if bin(i)[2:] not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for x in range(1,n+1):\n",
    "            print(bin(x)[2:])\n",
    "            if not bin(x)[2:] in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        def help(s, k, mi, ma):\n",
    "            st = set()\n",
    "            t = 0\n",
    "            for r in range(len(s)):\n",
    "                t = t * 2 + (int)(s[r])\n",
    "                if r >= k:\n",
    "                    t -= int(s[r - k]) << k\n",
    "                if r >= k - 1 and t >= mi and t <= ma:\n",
    "                    st.add(t)\n",
    "            return len(st) == ma - mi + 1\n",
    "        if n == 1:\n",
    "            return s.find('1') != -1\n",
    "        k = 30\n",
    "        while (1 << k) >= n:\n",
    "            k -= 1\n",
    "        if len(s) < (1 << (k - 1)) + k - 1 or len(s) < n - (1 << k) + k + 1:\n",
    "            return False\n",
    "        return help(s, k, 1 << (k - 1), (1 << k) - 1) and help(s, k + 1, 1 << k, n)\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/binary-string-with-substrings-representing-1-to-n/solutions/2264108/zi-chuan-neng-biao-shi-cong-1-dao-n-shu-ojtz8/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        m = len(s)\n",
    "        if (1 + m) * m // 2 < n:\n",
    "            return False\n",
    "        st = set()\n",
    "        for p in range(1, m + 1):\n",
    "            num = 0\n",
    "            for i in range(int(math.log(n)) + 5):\n",
    "                q = p + i\n",
    "                if q > m:\n",
    "                    break\n",
    "                num = num * 2 + int(s[q - 1])\n",
    "                if 1 <= num <= n:\n",
    "                    st.add(num)\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        self.s = s\n",
    "        if n == 1:\n",
    "            return \"1\" in s\n",
    "        \n",
    "        k, now_2 = 0, 1\n",
    "        while now_2 <= n:\n",
    "            k += 1\n",
    "            now_2 <<= 1\n",
    "        k -= 1\n",
    "        if len(s) < (1 << (k - 1)) + k - 1 or len(s) < n - (1 << k) + k + 1:\n",
    "            return False\n",
    "        else:\n",
    "            return self.judge(k, 1 << (k - 1), (1 << k) - 1) and self.judge(k + 1, 1 << k, n)\n",
    "    \n",
    "    def judge(self, k: int, min_num: int, max_num: int):\n",
    "        num_set = set()\n",
    "        now_t = 0\n",
    "        for i in range(len(self.s)):\n",
    "            now_t <<= 1\n",
    "            now_t += int(self.s[i])\n",
    "            if i >= k:\n",
    "                now_t -= int(self.s[i - k]) << k\n",
    "            if i >= k - 1 and (min_num <= now_t <= max_num):\n",
    "                num_set.add(now_t)\n",
    "        return len(num_set) == max_num - min_num + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1,n+1):\n",
    "            if str(bin(i))[2:] not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1, n+1):\n",
    "            sub = format(i, \"b\")\n",
    "            if sub not in s:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return '1' in s\n",
    "        \n",
    "        # m = s二进制字符串的长度\n",
    "        m = len(s)\n",
    "        # k = 数字n转为2进制后的长度 - 1\n",
    "        k = n.bit_length()-1\n",
    "        # 如果 m 的长度比无法表达 [1:n] 的所有数字 返回False\n",
    "        if m < max(n-(1<<k)+k+1, (1<<(k-1)) + k -1):\n",
    "            return False\n",
    "        \n",
    "        #对于长度为k的在[lower, upper]内的二进制数, 判断这些数是否s内都有\n",
    "        def check(k:int, lower:int, upper:int)->bool:\n",
    "            if lower > upper: return True\n",
    "            seen = set()\n",
    "            mask = (1<<(k-1))-1 # [1]*k-1\n",
    "            x = int(s[:k], 2) # x 为 s取前k-2位的二进制数字\n",
    "            # print(lower, k, len(s[:k]))\n",
    "\n",
    "            for c in s[k:]:\n",
    "                # &mask可以去掉最高比特位, 从而实现滑窗的'出'\n",
    "                # <<1 | int(c) 为滑窗的'入'\n",
    "                x = ((x & mask) << 1) | int(c) #去掉最高位后左移, 添加新的一位\n",
    "                if lower <= x <= upper:\n",
    "                    seen.add(x)\n",
    "            return len(seen) == upper-lower+1\n",
    "        \n",
    "        return check(k, n//2+1, (1<<k)-1) and check(k+1, 1<<k, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for x in range(1,n+1):\n",
    "            if not bin(x)[2:] in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # ans=0\n",
    "        # m=len(s)\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[m-i-1]=='1':\n",
    "        #         ans+=2**(i)\n",
    "        # print(ans)\n",
    "        # if ans==0:\n",
    "        #     return False\n",
    "        # if n==1:\n",
    "        #     return True\n",
    "        # for i in range(n,1,-1):\n",
    "        #     if ans%i!=0 and ans%i!=1:\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "\n",
    "        if n == 1:\n",
    "            return '1' in s\n",
    "\n",
    "        m = len(s)\n",
    "        k = n.bit_length() - 1\n",
    "        if m < max(n - (1 << k) + k + 1, (1 << (k - 1)) + k - 1):\n",
    "            return False\n",
    "\n",
    "        # 对于长为 k 的在 [lower, upper] 内的二进制数，判断这些数 s 是否都有\n",
    "        def check(k: int, lower: int, upper: int) -> bool:\n",
    "            if lower > upper: return True\n",
    "            seen = set()\n",
    "            mask = (1 << (k - 1)) - 1\n",
    "            x = int(s[:k - 1], 2)\n",
    "            for c in s[k - 1:]:\n",
    "                # & mask 可以去掉最高比特位，从而实现滑窗的「出」\n",
    "                # << 1 | int(c) 即为滑窗的「入」\n",
    "                x = ((x & mask) << 1) | int(c)\n",
    "                if lower <= x <= upper:\n",
    "                    seen.add(x)\n",
    "            return len(seen) == upper - lower + 1\n",
    "        return check(k, n // 2 + 1, (1 << k) - 1) and check(k + 1, 1 << k, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "执行用时：44 ms, 在所有 Python3 提交中击败了43.59%的用户\n",
    "内存消耗：16 MB, 在所有 Python3 提交中击败了20.51%的用户\n",
    "2023年5月10日 13:10\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return len(s)*(len(s)+1)//2>=n and all([bin(i)[2:] in s for i in range(1,n+1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        sl = len(s)\n",
    "        st = set()\n",
    "        for i in range(sl):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            t = 1\n",
    "            j = i + 1\n",
    "            while t <= n:\n",
    "                st.add(t)\n",
    "                if j == sl:\n",
    "                    break\n",
    "                t = (t << 1) + ord(s[j]) - ord('0')\n",
    "                j += 1\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        def get_bit(num):\n",
    "            res = \"\"\n",
    "            while(num>0):\n",
    "                res += str(num%2)\n",
    "                num = num//2\n",
    "            return res[::-1]\n",
    "        for i in range(1,n+1):\n",
    "            if get_bit(i) not in s:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(n,0,-1):\n",
    "            subs=bin(i)[2:]\n",
    "            if subs not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(n, 0, -1):\n",
    "            k = bin(i)[2:]\n",
    "            if len(k) > len(s) or k not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        def get_bit(num):\n",
    "            res = \"\"\n",
    "            while(num>0):\n",
    "                res += str(num%2)\n",
    "                num = num//2\n",
    "            return res[::-1]\n",
    "        for i in range(1,n+1):\n",
    "            if get_bit(i) not in s:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return '1' in s\n",
    "        \n",
    "        # m = s二进制字符串的长度\n",
    "        m = len(s)\n",
    "        # k = 数字n转为2进制后的长度 - 1\n",
    "        k = n.bit_length()-1\n",
    "        # 如果 m 的长度比无法表达 [1:n] 的所有数字 返回False\n",
    "        if m < max(n-(1<<k)+k+1, (1<<(k-1)) + k -1):\n",
    "            return False\n",
    "        \n",
    "        #对于长度为k的在[lower, upper]内的二进制数, 判断这些数是否s内都有\n",
    "        def check(k:int, lower:int, upper:int)->bool:\n",
    "            if lower > upper: return True\n",
    "            seen = set()\n",
    "            mask = (1<<(k-1))-1 # [1]*k-1\n",
    "            x = int(s[:k], 2) # x 为 s取前k-2位的二进制数字\n",
    "            # print(lower, k, len(s[:k]))\n",
    "\n",
    "            for c in s[k:]:\n",
    "                # &mask可以去掉最高比特位, 从而实现滑窗的'出'\n",
    "                # <<1 | int(c) 为滑窗的'入'\n",
    "                x = ((x & mask) << 1) | int(c) #去掉最高位后左移, 添加新的一位\n",
    "                if lower <= x <= upper:\n",
    "                    seen.add(x)\n",
    "            return len(seen) == upper-lower+1\n",
    "        \n",
    "        return check(k, n//2+1, (1<<k)-1) and check(k+1, 1<<k, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1, n+1):\n",
    "            k = str(bin(i))[2:]\n",
    "            if len(k) > len(s) or k not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        def convert(n):\n",
    "            v=1\n",
    "            while v<=n//2:\n",
    "                v*=2\n",
    "            res=''\n",
    "            while v>0:\n",
    "                if n<v:\n",
    "                    res+='0'\n",
    "                else:\n",
    "                    res+='1'\n",
    "                    n-=v\n",
    "                v//=2\n",
    "            return res\n",
    "        for i in range(1,n+1):\n",
    "            if s.find(convert(i))==-1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1, n+1):\n",
    "            if s.find(bin(i)[2:]) == -1:\n",
    "                return False\n",
    "                break\n",
    "            else:\n",
    "                pass\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # 4 = \"100\"\n",
    "        # 如果 4 符合 那么 2 也符合\n",
    "        # 所以应该只要判断 n ~ n / 2 之间的数\n",
    "\n",
    "\n",
    "        for i in range(n, n >> 1, -1):\n",
    "            x = bin(i)[2:]\n",
    "            if x not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        for i in range(1, n + 1):\n",
    "            binary_representation = bin(i)[2:]\n",
    "            if binary_representation not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # for i in range(1, n+1):\n",
    "        #     sub = format(i, \"b\")\n",
    "        #     if sub not in s:\n",
    "        #         return False\n",
    "        # return True \n",
    "\n",
    "        # return all([format(i, \"b\") in s for i in range(1, n+1)])  # 超时了。。。\n",
    "\n",
    "        return all(bin(i)[2:] in s for i in range(1, n + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(1, n + 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        m = len(s)\n",
    "        st = set()\n",
    "        for p in range(1, m + 1):\n",
    "            num = 0\n",
    "            for i in range(int(math.log(n)) + 5):\n",
    "                q = p + i\n",
    "                if q > m:\n",
    "                    break\n",
    "                num = num * 2 + int(s[q - 1])\n",
    "                if 1 <= num <= n:\n",
    "                    st.add(num)\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        m = len(s)\n",
    "        st = set()\n",
    "        for p in range(1, m + 1):\n",
    "            num = 0\n",
    "            for i in range(31):\n",
    "                q = p + i\n",
    "                if q > m:\n",
    "                    break\n",
    "                num = num * 2 + int(s[q - 1])\n",
    "                if 1 <= num <= n:\n",
    "                    st.add(num)\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n > 1000:\n",
    "            return False\n",
    "        return all(bin(i)[2:] in s for i in range(n, n // 2, -1))\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/binary-string-with-substrings-representing-1-to-n/solutions/2265319/python3javacgotypescript-yi-ti-yi-jie-na-cls1/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        seen = set()\n",
    "        s = list(map(int, s))\n",
    "        for i, x in enumerate(s):\n",
    "            if x == 0:\n",
    "                continue\n",
    "            j = i + 1\n",
    "            while x <= n:\n",
    "                seen.add(x)\n",
    "                if j == len(s):\n",
    "                    break\n",
    "                x = (x << 1) | s[j]\n",
    "                j += 1\n",
    "        return len(seen) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        m = len(s)\n",
    "        st = set()\n",
    "        for p in range(1, m + 1):\n",
    "            num = 0\n",
    "            for i in range(32):\n",
    "                q = p + i\n",
    "                if q > m:\n",
    "                    break\n",
    "                num = num * 2 + int(s[q - 1])\n",
    "                if 1 <= num <= n:\n",
    "                    st.add(num)\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        seen = set()\n",
    "        s = list(map(int, s))  # 把 s[i] 全部转成 int\n",
    "        for i, x in enumerate(s):\n",
    "            if x == 0: continue  # 二进制数从 1 开始\n",
    "            j = i + 1  # 下一个字符的下标\n",
    "            while x <= n:\n",
    "                seen.add(x)\n",
    "                if j == len(s): break\n",
    "                x = (x << 1) | s[j]  # 子串 s[i:j+1] 的二进制数\n",
    "                j += 1\n",
    "        return len(seen) == n\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        if n>302:# 1000lg2=301.03  s最多表示302位的数\n",
    "            return False\n",
    "        for i in range(1,n+1):\n",
    "            if str(bin(i))[2:] not in s:#i转为二进制不在\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return len(s)*(len(s)+1)//2>=n and all([bin(i)[2:] in s for i in range(1,n+1)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        # if n==1:\n",
    "        #     return \"1\" in s\n",
    "        print('a', 'a' in 'apple')\n",
    "        for i in range(1,n+1):\n",
    "            i = str(bin(i))\n",
    "            print(i[2:])\n",
    "            print(i in s)\n",
    "            if i[2:] in s:\n",
    "                \n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        contract={'0':0,'1':1}\n",
    "        remember={}\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            count=0\n",
    "            bit=0\n",
    "            for j in range(i,-1,-1):\n",
    "                count=count+contract[s[j]]*pow(2,bit)\n",
    "                bit+=1\n",
    "                if count>n:\n",
    "                    break\n",
    "                else:\n",
    "                    remember[count]=count\n",
    "        \n",
    "        if sum(i for i in remember.values())==n*(n+1)/2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(n,0,-1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "time complex: O(mlogn),the m is the length of s, for a certain i,the inner loop time complex is O(logn) \n",
    "space complex: O(min(mlogn, n))\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        sl = len(s)\n",
    "        st = set()\n",
    "        for i in range(sl):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            t = 1\n",
    "            j = i + 1\n",
    "            while t <= n:\n",
    "                st.add(t)\n",
    "                if j == sl:\n",
    "                    break\n",
    "                t = (t << 1) + int(s[j])\n",
    "                j += 1\n",
    "        return len(st) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queryString(self, s: str, n: int) -> bool:\n",
    "        return all(bin(i)[2:] in s for i in range(n, 0, -1))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
